Reconstruct Itinerary

Understand and solve the interview question "Reconstruct Itinerary".

Description#

Assume we have an array of airline tickets represented as pairs of departure and arrival airports like [from, to]. We have to reconstruct the itinerary in order. All tickets belong to a man who departs from a specified location, e.g., JFK. Therefore, the itinerary must begin with JFK. There might be multiple valid itineraries; you must return the itinerary with the smallest lexical order.

Constraints#

Consider the following constraints:

  • 1 <= tickets.length <= 300
  • tickets[i].length must be 2.
  • fromi.lengthfrom_i.length, toi.lengthto_i.length == 3
  • fromifrom_i and toito_i consist of uppercase English letters.
  • Specified departure must be the start point of itinerary.
  • fromifrom_i and toito_i would not be equal.
  • Must use all the tickets but only once.

Let’s try to understand the problem with the help of an example:

JFK
JFK
ATI
ATI
LHR
LHR
SAC
SAC
SJF
SJF
Tickets = [["JFK","ATI"] , ["ATI","LHR"] , ["SAC","SJF"] , ["LHR","SAC"]]
Tickets = [["JFK","ATI"] , ["ATI","LHR"] , ["SAC","SJF"] , ["LHR","SAC"]]
Viewer does not support full SVG 1.1
The valid itinerary

Coding exercise#

Reconstruct itinerary

Solution#

We have an array containing departure and arrival pairs. We assume this problem as a graph, where the vertices of the graph represent airports and edges represent a flight between the airports.

Let’s see an algorithm for the described problem below:

  1. First, we create a hash map with keys for each departure point. The value for a given key is an alphabetically sorted list of all airports to which the passenger flew from the airport represented by the given key.

  2. Next, we will append the start vertex to a string.

  3. Then, we will perform a post-order depth-first search (DFS) from the start vertex where the visit operation comprises appending a visited vertex to a list of strings.

  4. Once all vertices have been visited, reverse the list to get the result.

This way, we will get a valid itinerary that visits all the airports. We could assume the algorithm as the postorder depth-first search in a graph, with a fixed start vertex.

Let’s see the following illustration to understand this algorithm.

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

1 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

2 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

3 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

4 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

5 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

6 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

7 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

8 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

9 of 10

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

10 of 10

We will use the built-in nature of lists in Elixir, which takes O(1)O(1) time to extract an element from the top of the array. For this, we have to store the array in descending order.

Let’s see the following illustration after applying the described changes.

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

1 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

2 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

3 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

4 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

5 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

6 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

7 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

8 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

9 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

10 of 11

Created with Fabric.js 3.6.6
Reconstruct a valid itinerary

11 of 11

Let’s have a look at the solution code below:

Reconstruct itinerary

Complexity measures#

Time complexity Space complexity
O(EO(E loglog E)E) O(V+E)O(V+E)

Time complexity#

  • First, we add tickets into the map object. The time complexity of this operation is O(E)O(E), where E is the number of flights.

  • The dfs() method performs the pop() method in O(1)O(1) time, so, the total time complexity of the dfs() method will be O(V+E)O(V+E), where V represents the number of airports and E represents the number of flights.

  • The sort() method takes O(EO(E loglog E)E) time.

The worst-case time complexity of the sort() method is dominant. Therefore, the time complexity of the detect_itinerary() method would be O(EO(E loglog E)E) in the worst case.

Space complexity#

The worst-case space complexity of this problem is O(V+E)O(V+E) where V is the number of airports and E is the number of flights. The maximum function call stack depth for the dfs() function is O(E)O(E). As a result, the total space complexity of the detect_itinerary() method will be O(V+2E)O(V+2E) = O(V+E)O(V+E).

Restore IP Addresses

Text Justification